(1) Field of the Invention
This invention relates to a modular multiplication apparatus which performs modular multiplications.
(2) Description of the Prior Art
Recently, as the encryption has been sophisticated in the field of communications, the encryption requires various calculation apparatuses.
For example, modular multiplication apparatuses for performing modular multiplications are used in the elliptic curve cryptosystem. It should be noted here that the xe2x80x9cmodular multiplicationxe2x80x9d indicates an operation denotes as xe2x80x9c(a*b) mod p,xe2x80x9d where a, b, and p are integers respectively representing a multiplicand, a multiplier, and a modulus. This operation is also referred to as a modulo p multiplication of (a*b), and (a*b) mod p is also referred to as residue, or modular multiplication value.
FIG. 1 shows the construction of a conventional modular multiplication apparatus.
It is assumed that values a, b, and p used in the operations performed by the conventional modular multiplication apparatus are each as small as 4 bits, for the sake of conveniences.
The modular multiplication apparatus 1 includes a product calculating unit 2, a residue calculating unit 3, and a control unit 4.
The product calculating unit 2, including a multiplicand register 5 (4-bit), an adder 6 (4-bit), and a product register 7 (9-bit), calculates a*b (a multiplication of multiplicand a and multiplier b) under control of the control unit 4.
The following is a description of the procedures by which the control unit 4 controls the product calculating unit 2.
Step 1: The control unit 4 allows the multiplicand register 5 to store the multiplicand a, allows the lower four bits of the product register 7 to store the multiplier b, and allows the higher five bits of the product register 7 to store 0s.
Step 2: The control unit 4 judges whether the least significant bit (LSB) of the product register 7 is 0 or 1. When having judged that the LSB is 1, the control unit 4 allows the adder 6 to add four bits out of the higher five bits excluding the most significant bit (MSB) stored in the product register 7 to the multiplicand a stored in the multiplicand register 5, and allows the higher five bits of the product register 7 to store the addition result.
Step 3: The control unit 4 performs a right shift of one bit on the value stored in the product register 7.
Step 4: The control unit 4 repeats Steps 2 and 3 four times.
When the loop including Steps 2 and 3 has been executed four times, the product register 7 stores the product a*b.
The residue calculating unit 3 includes a modulus register 8 (4-bit), an adder 9 (5-bit), and a residue register 10 (13-bit). The residue calculating unit 3 calculates, under control of the control unit 4, (a*b) mod p in the same manner as a calculation by manual writing. Note that the residue output from the residue calculating unit 3 is a 5-bit value with a sign bit.
The following is a description of the procedures by which the control unit 4 controls the residue calculating unit 3.
Step 5: The control unit 4 allows the modulus register 8 to store the modulus p, allows the lower eight bits of the residue register 10 to store the product (a*b) read from the product register 7, and allows the higher five bits of the residue register 10 to store 0s.
Step 6: The control unit 4 performs a left shift of one bit on the value stored in the residue register 10.
Step 7: The control unit 4 allows the adder 9 to subtract the modulus p read from the modulus register 8 from the value read from the higher five bits of the residue register 10 and to store the subtraction result value in the higher five bits of the residue register 10.
Step 8: The control unit 4 judges whether the value stored in the higher five bits of the residue register 10 is positive or negative based on the MSB. When having judged that the value is negative (the MSB is 1), the control unit 4 allows the adder 9 to add up the value stored in the higher five bits of the residue register 10 and the modulus p stored in the modulus register 8 to restore the previous value (the value before the subtractions performed in Step 7) to the register 10.
Step 9: The control unit 4 repeats Steps 6 to 8 eight times.
When the loop including Steps 6 to 8 has been executed eight times, the higher five bits of the residue register 10 stores the residue (a*b) mod p.
In the conventional modular multiplication apparatus 1, 4-bit addition operations are enough for the adder 6 and adder 9 since the values a, b, and p are each as small as 4-bit, and the number of executions of a loop is as small as four times in the product calculating unit 2 and as eight times in the residue calculating unit 3. However, in practice, the values a, b, and p used in the elliptic curve cryptosystem are each as great as 160-bit, for example. Accordingly, the adder 6 and adder 9 will be required to perform 160-bit addition operations if the apparatus 1 is adjusted to deal with values 160-bit values a, b, and p, for example. This results in an increase in the circuit size which is one of the problems of the conventional modular multiplication apparatus 1. Also, in this case, the number of executions of a loop is as great as 160 in the product calculating unit 2 and as 320 in the residue calculating unit 3. This results in an increase in the time taken for performing operations, which is another problem of the conventional apparatus 1.
The U.S. Pat. No. 5,144,574, Modular Multiplication Method and the System for Processing Data discloses a modular multiplication method which relates to the above operation-time problem.
According to this method, the residue (a*b) mod p is obtained by the following procedure: a partial product is calculated by multiplying the multiplicand a by each two bits of the multiplier b in order from the MSB; each time the partial product is obtained, a partial residue is calculated by subtracting an integral multiple of the modulus p from the calculated partial product; and the residue (a*b) mod p is obtained by accumulating the calculated partial products.
Compared with the first conventional method, this method reduces the number of executions of the loop and the operation time since the partial product is calculated for each two bits of the multiplier b while in the first method, the product is calculated for each bit.
However, the time reduced by the second conventional method is not so much when the values a, b, and p to be dealt with are large.
It is therefore an object of the present invention to provide a modular multiplication apparatus which is achieved in a small circuit and performs calculations at high speed.
The above object is fulfilled by a modular multiplication apparatus for calculating a congruent value of a modulo P multiplication of a product of a multiplicand a and a kb-bit multiplier b, where P is k-bit, the congruent value being obtained from a following formula:             accumulated      ⁢              xe2x80x83            ⁢      value        =                  ∑                  i          =          0                          [                      [                          kb              /              s                        ]                    ]                    ⁢              xe2x80x83            ⁢                        C          ⁡                      (            i            )                          *                  b          ⁡                      [                                                            s                  *                  i                                +                s                -                1                            :                              s                *                i                                      ]                                ,
where [[kb/s]] represents integers included in quotient kb/s, i represents integers in a range of 0 to [[kb/s]],
C(i) is represented by a recurrence formula, and
C(i)=a(i=0) 
C(i)=(C(ixe2x88x921)*2s) mod P(ixe2x89xa71), 
C(i) (intermediate value) is a congruent value of a modulo P multiplication of a product (a preceding intermediate value*2S), where the congruent value is calculated recurrently, an initial intermediate value is the multiplicand a, and the product being equal to the preceding intermediate value shifted s bits, b[s*i+sxe2x88x921:s*i] represents s-bit, partial multipliers included in the multiplier b at places from 2s*i+sxe2x88x921 to 2s*i, the modular multiplication apparatus comprising: a table unit which prestores residues of modulo p multiplications of (m-bit value)*2k, where m is an integer s or larger; an intermediate value calculation unit for outputting the multiplicand a as an intermediate value C(0) first time (i=0), and second time and after (ixe2x89xa71), performing a shift of s bits on a preceding intermediate value C(ixe2x88x921) to acquire a shifted intermediate value, referring to the table unit to read out a residue corresponding to m bits adjacent to lower k bits of the shifted intermediate value, and obtaining another intermediate value C(i) by adding up the read-out residue and the lower k bits, where partial product C(i)*b[s*i+sxe2x88x921:s*i] is obtained for each combination of C(i) and b[s*i+sxe2x88x921:s*i] corresponding to each other, and each partial product C(i)*b[s*i+sxe2x88x921:s*i] is accumulated in sequence.
In the above-stated construction, the table unit prestores residues of modulo p multiplications of (m-bit value)*2k, where the m-bits values respectively correspond to values from decimal values 0 to 2mxe2x88x921. The intermediate value calculation unit, when ixe2x89xa71, refers to the table unit to read out a residue corresponding to m bits adjacent to lower k bits of the left-shifted intermediated value, that is, a residue of modulo p multiplication of (higher m bits)*2k. The intermediate value calculation unit calculates a residue or a congruent value of modulo p multiplications of the left-shifted intermediate value by adding up the read-out residue and the lower k bits.
Here, the lower k bits of the left-shifted intermediate value represent a residue itself or a congruent value of modulo p multiplication. The congruent value is larger than and the closest to the residue. Accordingly, to obtain a residue of modulo p multiplication of a left-shifted intermediate value or a congruent value closest to the residue, the intermediate value calculation unit is only required to obtain a residue and add up the residue and the lower k bits. That is to say, the intermediate value calculation unit calculates in short time a residue or a congruent value of modulo p multiplication of the left-shifted intermediate value by referring to the table unit to obtain the residue for the higher m bits.
If the residue or congruent value of modulo p multiplication of the left-shifted intermediate value was to be calculated with the procedure used by the conventional residue calculating unit 3 of the conventional modular multiplication apparatus 1, the intermediate value calculation unit would repeat the loop process (steps 6-8) a plurality of times. More specifically, the number of repetitions corresponds to the number of shifts and the number of bits of the intermediate value. In contrast, the intermediate value calculation unit of the present invention performs the same at a higher speed since the unit is only required to perform one reference to the table unit and one addition to acquire the residue or congruent value of modulo p multiplication of the left-shifted intermediate value, resulting in an achievement of a high-speed modular multiplication.
In the above modular multiplication apparatus, the intermediate value calculation unit may include: a first hold unit for holding an intermediate value; a shift unit for obtaining the shifted intermediate value by performing a shift of s bits on the intermediate value held by the first hold unit in correspondence to the partial multiplier b[s* i+sxe2x88x921:s*i]; a division unit for dividing the shifted intermediate value into a higher data and a lower data, where the higher data is composed of m bits adjacent to lower k bits of the shifted intermediate value, and the lower data is composed of the lower k bits; a read unit for referring to the table unit to read out a residue corresponding to the higher data; and an addition unit for calculating another intermediate value by adding up the read-out residue and the lower data, where the first hold unit updates the intermediate value to the other intermediate value calculated by the addition unit each time the addition unit calculates a new intermediate value, and outputs the multiplicand as an intermediate value first time, and outputs the updated intermediate value second time and after.
With the above-stated construction, each component of the intermediate value calculation unit is achieved using a general-purpose hardware device in a simple construction. More specifically, the first hold unit is achieved by a register, the shift unit a shifter, and the addition unit an adder. Also, the division unit is achieved by an m-bit bus and a k-bit bus connected to the higher m-bit part and the lower k-bit part of the shifter. The intermediate value calculation unit including these components recurrently calculates the intermediate value C(i).
In the modular multiplication apparatus, the table unit may include: a memory device which prestores residues of modulo p multiplications of (m-bit value)*2k, where storage areas of residues respectively correspond to addresses to be input, and the addresses further correspond to m-bit values.
With the above-stated construction, the table unit is achieved by one memory device. The memory device prestores residues of modulo p multiplications of (m-bit value)*2k, where the m-bit values respectively correspond to values from decimal values 0 to 2mxe2x88x921. On receiving the higher m bits from the read unit as an address, the memory device outputs a residue which is stored in an area having the received address. With such an arrangement, it is possible for the intermediate value calculation unit to obtain the residue corresponding to the higher m bits in a short time by referring to the memory device only once.
In the modular multiplication apparatus, the m-bit value may be divided into an m1-bit value and an m2-bit value, where the m1-bit value is composed of lower m1bits and the m2-bit value is composed of higher m2 bits, where m=m1+m2, each m-bit value corresponds to a combination of an m1-bit value and an m2-bit value, the table unit includes: a first part table unit which prestores residues of modulo p multiplications of (m1-bit value)*2k; and a second part table unit which prestores residues of modulo p multiplications of (m2-bit value)*2k+m1, where the addition unit adds up residues respectively read out from the first part table unit and the second part table unit and the lower data.
In the above-stated construction, the table unit includes: the first part table corresponding to the higher m1 bits of the m bits; and the second part table corresponding to the lower m2bits. The first part table stores *2m1 residues corresponding to the higher m1 bits. The second part table stores *2m2 residues corresponding to the lower m2 bits. As understood from this, the sum of the numbers of residues stored in the first and second part tables is smaller than the number of residues stored in one memory device. Therefore, the table unit is also achieved by two memory devices with small capacity.
In the above modular multiplication apparatus, the m bits may be divided into t bit-sequences respectively having m1 bits, m2bits, . . . mt bits in order from lower bits, where 3xe2x89xa6txe2x89xa6m, each m-bit value corresponds to a combination of values respectively represented by t bit-sequences mi, where i represents each integer in a range of 1 to t, the table unit includes: t partial table unit Ti which each prestore residues of modulo p multiplications of (mi-bit value)*2k+x, where x=m1+m2+. . . +m(ixe2x88x9212), and the addition unit adds up t residues respectively read out by the read unit from the t partial table unit Ti and the lower data.
With the above-stated construction, the table unit includes t partial tables which respectively correspond to the values of t partial bits making up the m bits. With this construction, the number of residues stored in each partial table is small.
In the above modular multiplication apparatus, the m bits may be divided into t bit-sequences respectively having m1 bits, m2 bits, . . . mt bits in order from lower bits, where 2xe2x89xa6txe2x89xa6m, the table unit includes: t partial table unit Ti which each prestore residues of modulo p multiplications of (a value represented by bit-sequences mi)*2k+x, where       x    =                  ∑                  j          =          1                          i          -          1                    ⁢              xe2x80x83            ⁢      mj        ,
the addition unit adds up t residues respectively read out by the read unit from the t partial table unit Ti and the lower data, where a result of this addition is equivalent to the other intermediate value.
With the above-stated construction, the table unit includes t partial tables which respectively correspond to the values of t partial bits making up the m bits. With this construction, the number of residues stored in each partial table is small.
In the above modular multiplication apparatus, each of the t partial table unit Ti may prestore each of the residues as k-bit data.
The above modular multiplication apparatus may further comprise: an accumulation unit; and a correction unit, where the accumulation unit includes: a third register for holding 0 as an initial value; and an adder for adding up the partial products C(i)*b[s*i+sxe2x88x921:s*i] and the accumulated value stored in the third register and storing a result of this addition into the third register as another accumulated value, where the correction unit includes: a correction value hold unit for holding a correction value being an integral multiple of P; and a correction control unit for allowing the adder to subtract the correction value held by the correction value hold unit from the accumulated value held by the third register when the accumulated value is larger than a predetermined value.
With the above-stated construction, overflows in the third register are prevented from occurring since the adder subtracts the correction value from the accumulated value when the accumulated value is larger than a predetermined value.
In the above modular multiplication apparatus, the third register may include a sign bit, the correction control unit allows the adder to subtract the correction value from the accumulated value at the same time when the adder adds up the partial product and the accumulated value stored in the third register when the accumulated value is positive, and the correction value is an integral multiple of P and the absolute value of the correction value is equivalent to or smaller than a maximum value (t+1) (2Sxe2x88x921)P of the partial product.
With the above-stated construction, overflows in the third register are prevented from occurring since the correction control unit allows the adder to subtract the correct value from the accumulated value stored in the third register when the accumulated value is positive (sign bit is 1). Also, the last accumulated value is smaller than or close to P after the correction since the correction value is an integral multiple of P and is the maximum value (t+1) (2sxe2x88x921)P of the partial product or smaller.
In the above modular multiplication apparatus, the modulo P multiplication may satisfy P=2kxe2x88x92xcex1, each of the t partial table unit Ti prestores each of the residues as k3-bit data, where k3 is equivalent to the number of bits in t* 2m*xcex1, and xcex1 is a constant defined to satisfy a condition that k3 is smaller than k.
With the above-stated construction, each residue stored in the partial tables Ti is k3-bit or smaller. This reduces the number of bits of each residue output from the partial tables. The bit width of the addition unit is also limited in accordance with the limitation that each residue output from the partial tables is k3-bit or smaller.
In the above modular multiplication apparatus, each of the t partial table unit Ti may include 2mi entries which respectively correspond to values in a range of 0 to (2mixe2x88x921) each having mi bits, where the jth m1+entry stores (jxe2x88x921)*2 . . . +m(ixe2x88x921)*xcex1, where j=1, . . . 2mi.
With the above-stated construction, the size of the partial table Ti is small since the number of entries is limited to as small as 2mixe2x88x921.
Here, suppose that xcex1 is u-bit. Then, the number of bits of the jth entry is limited to the sum of the number of bits of j, m1+. . . +m(ixe2x88x921), and u bits, at maximum. Accordingly, the bit width of the addition unit is also limited in accordance with this limitation.
The above modular multiplication apparatus may further comprise: a post-processing unit for using the table unit to obtain a residue of a modulo P multiplication of a last accumulated value having been corrected by the correction unit, where the last accumulated value is an accumulated value corrected by the correction unit in correspondence to a partial multiplier including the most significant bit of the multiplier.
With the above-stated construction, it is possible to make the last accumulated value smaller than P by allowing the post-processing unit to obtain the residue of modulo P multiplication of the last accumulated value.
The above object is also fulfilled by a modular multiplication apparatus for calculating a congruent value of a modulo P multiplication of a product of a multiplicand and a multiplier, where P is k-bit data, the modular multiplication apparatus comprising: an output unit for outputting, in order from lower bits, partial multipliers which are s-bit parts making up the multiplier, where s is an integer 2 or larger; a first calculation unit for obtaining shifted multiplicands by shifting the multiplicand in accordance with a place of each partial multiplier, and for calculating congruent values of a modulo p multiplication of respective shifted multiplicands, where the congruent values obtained here are referred to as intermediate values; a second calculation unit for calculating partial products by multiplying the partial multipliers output from the output unit by the corresponding intermediate values output from the first calculation unit; an accumulation unit for accumulating the partial products output from the second calculation unit and outputting an accumulated value; a correction unit for performing a correction so that the accumulated value does not exceed a predetermined number of bits by adding/subtracting an integral multiple of p to/from the accumulated value; and a control unit for allowing the first calculation unit, the second calculation unit, the accumulation unit, and the correction unit to repeatedly perform the respective operations for each of the partial multipliers output from the output unit, where the first calculation unit includes: a table unit which prestores residues of modulo p multiplications of (m-bit value)*2k, where ms is an integer s or larger, where the first calculation unit outputs the multiplicand as an intermediate value first time, and second time and after, obtains a shifted intermediate value by performing a shift of s bits on a preceding intermediate value, refers to the table unit to read out a residue corresponding to m bits adjacent to lower k bits of the shifted intermediate value, and calculates another intermediate value by adding up the read-out residue and the lower k bits.
With the above-stated construction, the first calculation unit, in the second round and after in the loop, refers to the table unit to read out a residue corresponding to the higher m bits excluding the lower k bits of the intermediate value left-shifted by s bits, and calculates a residue or congruent value of modulo P multiplication of the left-shifted intermediate value as an intermediate value by adding up read-out residue and the lower k bits. With this arrangement, the first calculation unit calculates the residue at high speed.
The second calculation unit calculates each partial product of each s-bit partial multiplier and the intermediate value. Accordingly, the second calculation unit performs the calculation of the partial product as many times as the number of partial multipliers. This allows the second calculation unit to calculate faster than the product calculating unit 2 of the conventional technique since the number of operations performed by the second calculation unit is reduced.
In the above modular multiplication apparatus, the first calculation unit may include: a first hold unit for holding an intermediate value; a shift unit for obtaining the shifted intermediate value by performing a shift of s bits on the intermediate value held by the first hold unit in correspondence to each partial multiplier output from the output unit second time and after; a division unit for dividing the shifted intermediate value into a higher data and a lower data, where the higher data is composed of m bits adjacent to lower k bits of the shifted intermediate value, and the lower data is composed of the lower k bits; a read unit for referring to the table unit to read out a residue corresponding to the higher data; and an addition unit for calculating another intermediate value by adding up the read-out residue and the lower data, where the first hold unit updates the intermediate value to the other intermediate value calculated by the addition unit, and outputs the multiplicand as an intermediate value first time, and outputs the updated intermediate value second time and after, and the second calculation unit calculates partial products by using the intermediate value held by the first hold unit.
With the above-stated construction, such component of the intermediate value calculation unit is achieved using a general-purpose hardware device in a simple construction. More specifically, the first hold unit is achieved by a register, the shift unit a shifter, and the addition unit an adder. Also, the division unit is achieved by an m-bit bus and k-bit bus connected to the higher m-bit part and the lower k-bit part of the shifter. The intermediate value calculation unit including these components recurrently calculates the intermediate value C(i).
In the above modular multiplication apparatus, the control unit may control a pipeline process which includes a first stage, a second stage, and a third state, and in the first stage, the control unit allows the output unit to output a partial multiplier and allows the first calculation unit to output an intermediate value, in the second stage, the control unit allows the second calculation unit to output a partial product, and in the third stage, the control unit allows the accumulation unit to accumulate partial products and allows the correction unit to perform correction.
With the above-stated construction, the speed of the calculation by the modular multiplication apparatus is further increased since the pipeline process adopted here enables each component to operate effectively.
In the above modular multiplication apparatus, the output unit may include: a multiplier hold unit for holding the multiplier as an initial value and outputting a partial multiplier which is composed of lower s bits of a value currently held in the multiplier hold unit; a shift right unit for performing a shift right of s bits on a value held by the multiplier hold unit and outputting the right-shifted value to the multiplier hold unit so that the right-shifted value is stored in the multiplier hold unit.
With the above-stated construction, the output unit is simply achieved by a register for holding the multiplier and a shifter for performing a shift right of s bits on the multiplier held by the register.
In the above modular multiplication apparatus, the second calculation unit may include: a judgment unit for judging whether all bits of the s-bit partial multiplier output from the output unit are 1; a first generation unit for generating a product of a multiplication of the intermediate value and 2S; and generating a negative value of the multiplicand; a second generation unit for generating a product of a multiplication of the intermediate value and a bit weight of each bit of the partial multiplier, where the product is equivalent to the intermediate value shifted by the number of bits corresponding to each bit weight; and a second addition unit for: adding up each value generated by the first generation unit when the judgement unit judges that the all bits are 1; and adding up products corresponding to bits being binary value xe2x80x9c1xe2x80x9d in the partial multiplier out of the products generated by the second generation unit when the judgment unit does not judge that the all bits are 1.
With the above-stated construction, the addition unit adds up: the product of multiplication of the intermediate value and 2S generated by the first generation unit; and the negative value of the multiplicand when the judgment unit judges that the all bits of the partial multiplier are 1. Here, in practice, the adder obtains a result of this subtraction by adding up the inverted value of the multiplicand and constant 1. Also, the addition of constant 1 is achieved by a carry-in. Accordingly, when all binary digits in the places of the multiplier are all xe2x80x9c1, xe2x80x9d the adder can obtain the product by performing two additions and one carry-in. This reduces the number of addition operations performed by the addition unit make it possible to reduce the circuit size of the addition unit.
In the above modular multiplication apparatus, the second generation unit may include: ith shift unit for obtaining a shifted intermediate value by performing a shift of i bits on the intermediate value calculated by the first calculation unit, wherein i represents integers in a range of 1 to (s-1), the first generation unit includes: sth shift unit for obtaining a shifted intermediate value by performing a shift of s bits on the intermediate value calculated by the first calculation unit; a complement generation unit for generating a one""s complement of the intermediate value; and a constant output unit for outputting a constant 1, wherein the second addition unit includes: a selection unit for: selecting the shifted intermediate value output from the sth shift unit, the one""s complement generated by the complement generation unit, and the constant 1 when the judgment unit judges that the all bits are 1; and selecting the intermediate value when a bit at a place of 20 of the partial multiplier has binary value xe2x80x9c1xe2x80x9d when the judgment unit does not judge that the all bits are 1; and selecting the shifted intermediate value output from the ith shift unit when a bit at a place of 2i of the partial multiplier has binary value xe2x80x9c1xe2x80x9d when the judgment unit does not judge that the all bits are 1; and an adder for calculating the partial product by adding up values selected by the selection unit.
With the above-stated construction, the first to (s-1) shift units are achieved by shifters which perform shift left of one bit to (s-1) bits. The sth shift unit is achieved by a shifter which performs a shift left of s bits. The complement generation unit is achieved by an inverter. As apparent from this, the first and second generation units can be achieved by general-purpose hardware devices. These components generate in advance candidate values which are to be added up by the addition unit. The selection unit selects candidate values to be added up by the addition unit in accordance with the values of the partial multipliers. The addition unit calculates the partial product by adding up the selected candidate values. With this construction, the second calculation unit calculates the partial product of the intermediate values at a plurality of places and the partial multipliers at high speed.
In the above modular multiplication apparatus, where s=3n, the partial multiplier may be divided into n 3-bit data sequences s1, . . . sn in order from lower bits, the second calculation unit includes: jth judgment unit for judging whether the 3-bit data sequence sj is (111)2, where j represents integers in a range of 1 to n, jth special generation unit for generating a product of I*(1000)2*23(j-1) (I representing the intermediate value) and generating N (N representing a negative value of I*23(jxe2x88x921)) when the jth judgment unit judges that the 3-bit data sequence sj is (111)2, where 23(j-1) corresponds to a place of the 3-bit data sequence sj; jth general generation unit for generating, for each bit of the 3-bit data sequence sj, products of multiplications of a logical value of a current bit, each bit weight of each bit in the s-bit partial multiplier, and the intermediate value when the jth judgment unit does not judge that the 3-bit data sequence sj is (111)2, where the product is equivalent to the intermediate value shifted by the number of bits corresponding to the bit weight; and a second addition unit for adding up the products generated by the jth special generation unit and the jth general generation unit.
In the above modular multiplication apparatus, the second calculation unit may include: ith shift unit for obtaining a shifted intermediate value by performing a shift of i bits on the intermediate value, where i represents integers in a range of 1 to s, where the jth general generation unit when j=1 uses shifted intermediate values obtained by the ith shift unit when i=1, 2, the jth general generation unit when jxe2x89xa01 uses shifted intermediate values obtained by the (3jxe2x88x923)th shift unit, (3jxe2x88x922)th shift unit, and the (3j1)th shift unit, the j special generation unit uses shifted intermediate values obtained by the 3jth shift unit, and the jth special generation unit and the (j+1) general generation unit share the 3jth shift unit.
In the above modular multiplication apparatus, the jth special generation unit may include: a complement generation unit for generating one""s complement of either of the intermediate value and the shifted intermediate value obtained by the (3jxe2x88x923)th shift unit; and a constant output unit for outputting the constant 1, the second addition unit includes: a selection unit for: selecting the shifted intermediate value output from the 3jth shift unit, the one""s complement generated by the complement generation unit of the jth special generation unit, and the constant 1 output from the constant output unit of the jth special generation unit when the jth judgment unit judges that the 3-bit data sequence sj is (111)2; selecting the intermediate value and outputs from the (3jxe2x88x922)th shift unit and the (3jxe2x88x921) shift unit when the jth judgment unit does not judge that the 3-bit data sequence s1 is (111)2; and selecting outputs from the (3jxe2x88x923)th shift unit, the (3jxe2x88x922)th shift unit, and the (3jxe2x88x921) shift unit when the jth judgment unit does not judge that the 3-bit data sequence sj except for the 3-bit data sequence s1 is (111)2; and an adder for calculating the partial product by adding up values selected by the selection unit.
The above modular multiplication apparatus may further comprise: a post-processing unit for using the division unit, the read unit, and the addition unit to obtain a residue of a module P multiplication of a last accumulated value having been corrected by the correction unit, where the last accumulated value is an accumulated value corrected by the correction unit in correspondence to the partial multiplier output last from the output unit.
With the above-stated construction, the post-processing unit calculates the residue of the modulo P multiplication of the last accumulated value using the division unit, read unit, and addition unit. It is possible with this arrangement for the post-processing unit to obtain the last accumulated value smaller than P.
The above object is also fulfilled by a modular multiplication apparatus for calculating a congruent value of a modulo P multiplication of a product of a multiplicand and a multiplier, where P is k-bit data, the modular multiplication apparatus comprising: an output unit for outputting, in order from lower bits, partial multipliers which are s-bit parts making up the multiplier, where s is an integer 2 or larger; a first calculation unit for obtaining shifted multiplicands by shifting the multiplicand in accordance with a place of each partial multiplier, and for calculating congruent values of a modulo p multiplication of respective shifted multiplicands, where the congruent values obtained here are referred to as intermediate values; a second calculation unit for calculating partial products by multiplying the partial multipliers output from the output unit by the corresponding intermediate values output from the first calculation unit; an accumulation unit for accumulating the partial products output from the second calculation unit and outputting an accumulated value; a correction unit for performing a correction so that the accumulated value does not exceed a predetermined number of bits by adding/subtracting an integral multiple of p to/from the accumulated value; and a control unit for allowing the first calculation unit, the second calculation unit, the accumulation unit, and the correction unit to repeatedly perform the respective operations for each of the partial multipliers output from the output unit, where the second calculation unit includes: a judgment unit for judging whether all bits of the s-bit partial multiplier output from the output unit are 1; a first generation unit for generating a product of the intermediate value*2s; and generating a negative value of the multiplicand; a second generation unit for generating a product of the intermediate value and a bit weight of each bit of the partial multiplier, where the product is equivalent to the intermediate value shifted by the number of bits corresponding to each bit weight; an addition unit for: adding up each value generated by the first generation unit when the judgment unit judges that the all bits are 1; and adding up products corresponding to bits being binary value xe2x80x9c1xe2x80x9d in the partial multiplier out of the products generated by the second generation unit when the judgment unit does not judge that the all bits are 1.
With the above-stated construction, the addition unit adds up: the product of multiplication of the intermediates value and 2s generated by the first generation unit; and the negative value of the multiplicand when the judgment unit judges that the all bits of the partial multiplier are 1. The number of addition operations performed by the addition unit is reduced when all bits of the partial multiplier are 1. This reduces the load on the addition unit. When the judgment unit does not judge that the all bits are 1, the addition unit adds up the products corresponding to binary values xe2x80x9c1xe2x80x9d in the partial multiplier out of the s products generated by the second generation unit by multiplying the intermediate value and each bit weight of the partial multiplier.
With such a construction, the second calculation unit calculates partial products of multiple-digit values in a short time. Here, if the calculation method of the second calculating unit 2 in the conventional technique was used, the loop of steps 2-3 would be repeated s times to obtain the partial product of the intermediate value and the partial multiplier. In contrast, the second calculating unit of the present invention obtains the same in one process. The modular multiplication apparatus of the present invention calculates residues or congruent values of modulo P multiplications of the product of the multiplicand and the multiplier by accumulating the obtained partial products.
The above object is also fulfilled by a multiplication apparatus comprising: a judgement unit for judging whether all bits of an n-bit multiplier are 1, where nxe2x89xa73; a generation unit for generating a value being a multiplicand*2n when the judgement unit judges that all bits are 1; a complement generation unit for generating one""s complement of the multiplicand when the judgement unit judges that all bits are 1; and an addition unit for adding up the value being a multiplicand*2n, one""s complement of the multiplicand, and constant 1.
With the above-stated construction, the addition unit adds up the product of multiplicand*2n generated by the generation unit, one""s complement of the multiplicand generated by the complement generation unit, and the constant 1 when the judgment unit judges that the all bits of the multiplier are 1. The sum of these values is equivalent to the product of the multiplicand and the multiplier. As apparent from this, when all bits of the multiplier are 1, the number of addition operations performed by the addition unit of the multiplication apparatus is reduced. This reduces the load on the addition unit and the circuit size of the addition unit.
In the above multiplication apparatus, the generation unit may be a shifter which performs a shift left of n bits and input 0 into each of lower n bits of the shifter.
The above object is also fulfilled by a multiplication apparatus which obtains a product by accumulating partial products which are obtained as results of multiplications of a multiplicand and partial multipliers making up a multiplier, the multiplication apparatus comprising: a division unit for dividing the multiplier into a plurality of n-bit partial multipliers, where nxe2x89xa73; a judgement unit for judging whether all bits of an n-bit multiplier are 1; a first generation unit for generating a partial product using a sum of the multiplicand*2n and a negative value of the multiplicand when the judgement unit judges that all bits are 1; a second generation unit for generating a partial product using the multiplicand* (a partial multiplier) when the judgement unit does not judge that all bits are 1; and an accumulation unit for accumulating partial products generated by the first generation unit and the second generation unit in sequence.
In the above multiplication apparatus, the first generation unit may include: a shift unit for performing a shift left of n bits on the multiplicand when the judgement unit judges that all bits are 1; a complement generation unit for generating one""s complement of the multiplicand; and an addition unit for adding up the multiplicand shifted by the shift unit, one""s complement of the multiplicand, and 1.
With the above-stated construction, the first generation unit generates: the product of multiplication of the multiplicand and 2n; and the negative value of the multiplicand when the judgment unit judges that the all bits of the partial multiplier are 1. The second generation unit generates: the partial product of multiplication of the multiplicand and partial multipliers. The accumulation unit obtains the product of the multiplicand and the multiplier by accumulating the partial products generated by the first and second generation units. The first generation unit includes a shifter for performing a shift left of n bits on the multiplicand, a complement generation unit for generating one""s complement of the multiplicand, and an addition unit for adding up the left-shifted multiplicand, one""s complement of the multiplicand, and one. With such a construction, when all bits of the partial multiplier are 1, the number of addition operations performed by the addition unit is greatly reduced. This reduces the circuit size of the addition unit.